function BinarySearchTree() {
  let Node = function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  };

  let root = null;

  //插入
  this.insert = (key) => {
    let newNode = new Node(key);

    //special case - first element
    if (root === null) {
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };

  let insertNode = (node, newNode) => {
    if (newNode.key < node.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  };

  this.getRoot = () => {
    return root;
  };

  //中序
  this.inOrderTraverse = (callback) => {
    inOrderTraverseNode(root, callback);
  };

  let inOrderTraverseNode = (node, callback) => {
    console.log("now node is => ", node);
    if (node !== null) {
      console.log(node, "left");
      inOrderTraverseNode(node.left, callback);
      callback(node.key);
      console.log(node, "right");
      inOrderTraverseNode(node.right, callback);
    }
  };

  //先序
  this.preOrderTraverse = (callback) => {
    preOrderTraverseNode(root, callback);
  };

  let preOrderTraverseNode = (node, callback) => {
    if (node !== null) {
      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  };

  //后序
  this.postOrderTraverse = (callback) => {
    postOrderTraverseNode(root, callback);
  };

  let postOrderTraverseNode = (node, callback) => {
    if (node !== null) {
      postOrderTraverseNode(node.left, callback);
      postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  };

  //搜索最小
  this.min = () => {
    return minNode(root);
  };

  let minNode = (node) => {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }

      return node.key;
    }
    return null;
  };

  //搜索最大
  this.max = () => {
    return maxNode(root);
  };

  let maxNode = (node) => {
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }

      return node.key;
    }
    return null;
  };

  //搜索任意
  this.search = (key) => {
    return searchNode(root, key);
  };

  let searchNode = (node, key) => {
    if (node === null) {
      return false;
    }
    if (key < node.key) {
      return searchNode(node.left, key);
    } else if (key > node.key) {
      return searchNode(node.right, key);
    } else {
      //element is equal to node.item
      return true;
    }
  };

  this.remove = (element) => {
    root = removeNode(root, element);
  };

  let removeNode = (node, element) => {
    if (node === null) {
      return null;
    }

    if (element < node.key) {
      node.left = removeNode(node.left, element);
      return node;
    } else if (element > node.key) {
      node.right = removeNode(node.right, element);
      return node;
    } else {
      //element is equal to node.item

      //handle 3 special conditions
      //1 - a leaf node
      //2 - a node with only 1 child
      //3 - a node with 2 children

      //case 1
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }

      //case 2
      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }

      //case 3
      let aux = findMinNode(node.right);
      node.key = aux.key;
      node.right = removeNode(node.right, aux.key);
      return node;
    }
  };

  let findMinNode = (node) => {
    while (node && node.left !== null) {
      node = node.left;
    }
    return node;
  };
}

let tree = new BinarySearchTree();

tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

console.log("********* in-order transverse ***********");
function printNode(value) {
  console.log(value);
}
// tree.inOrderTraverse(printNode);

// console.log('********* pre-order transverse ***********');
// tree.preOrderTraverse(printNode);

// console.log('********* post-order transverse ***********');
// tree.postOrderTraverse(printNode);

// console.log('********* max and min ***********');
// console.log(tree.max());
// console.log(tree.min());
// console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.');
// console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.');

// console.log('********* remove 6 ***********');
// tree.remove(6);
// tree.inOrderTraverse(printNode);

// console.log('********* remove 5 ***********');
// tree.remove(5);
// tree.inOrderTraverse(printNode);

// console.log('********* remove 15 ***********');
// tree.remove(15);
// tree.inOrderTraverse(printNode);

// console.log('********* raw data structure ***********');
// console.log(tree.getRoot());
